/*
==================================================================
* 版权所有 © 2025 CaryXiong
* Copyright (C) 2025 CaryXiong(a1816101108@outlook.com)
*
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
===================================================================
*/


#include<iostream>
using namespace std;



template<class DataType>
class LineSearch{
    public:
        LineSearch(DataType data[], int length);
        int SeqSearch(DataType k);
        int BinSearch1(DataType k);
        int BinSearch2(int low, int high, DataType k);
    private:
        DataType *data;
        int length;
};


template<class DataType>
LineSearch<DataType> :: LineSearch(DataType data[], int length){
    this->length = length;
    this->data = new DataType[length+1];
    for(int i=0; i<length; i++){
        this->data[i+1] = data[i];
    }
}


template<class DataType>
int LineSearch<DataType> :: SeqSearch(DataType k){
    // 顺序查找算法
    int i = length;
    this->data[0] = k;
    while(this->data[i] != k) i--;
    return i;
}

template<class DataType>
int LineSearch<DataType> :: BinSearch1(DataType k){
    // 折半查找非递归算法
    int mid, low=1, high=length;
    while (low<=high)
    {
        mid = (high+low)/2;
        if(k < data[mid]) high = mid-1;
        else if(k > data[mid]) low = mid+1;
        else return mid;
    }
    return 0;
}

template<class DataType>
int LineSearch<DataType> :: BinSearch2(int low, int high, DataType k){
    // 折半查找递归算法

    if(low > high) return 0;
    else{
        int mid = (low+high)/2;
        if(k < data[mid]) return BinSearch2(low, mid-1, k);
        else if(k > data[mid]) return BinSearch2(mid+1, high, k);
        else return mid;
    }
}




int main(){
    int a[10] = {1,2,3,4,5,6,7,8,9,10};
    LineSearch<int> L(a, 10);
    
    cout << "**********顺序表的顺序查找算法**********" << endl;
    cout << "查找元素6的位置：" << L.SeqSearch(6);
    cout << endl << endl;

    cout << "**********顺序表的折半查找非递归算法**********" << endl;
    cout << "查找元素4的位置：" << L.BinSearch1(4);
    cout << endl << endl;

    cout << "**********顺序表的折半查找递归算法**********" << endl;
    cout << "查找元素10的位置：" << L.BinSearch2(1,10,10);
    cout << endl << endl;
}